package com.imooc.distributedemo.resume.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode152 乘积最大子数组
 */
public class Solution152 {
    public static void main(String[] args) {
        int[] nums = {2,3,-2,4};
        int result = maxProduct(nums);
        System.out.println(result);
    }

    public static int maxProduct(int[] nums) {
        if(null==nums||nums.length<1){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }

        int length = nums.length;
        int[] maxF = new int[length];
        int[] minF = new int[length];
        System.arraycopy(nums, 0, maxF, 0, length);
        System.arraycopy(nums, 0, minF, 0, length);
        for (int i = 1; i < length; ++i) {
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
        }
        int ans = maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, maxF[i]);
        }




        List<List<Integer>> result = new ArrayList<>();
        for (int start = 0; start < nums.length; start++) {
            for (int end = start; end < nums.length; end++) {
                List<Integer> subarray = new ArrayList<>();
                for (int i = start; i <= end; i++) {
                    subarray.add(nums[i]);
                }
                result.add(subarray);
            }
        }
        int max = 0;
        for (int i = 0; i < result.size(); i++) {
            List<Integer> datas = result.get(i);
            int mx = 1;
            for (int j = 0; j < datas.size(); j++) {
                mx *= datas.get(j);
            }
            max = Math.max(max,mx);
        }
        return max;
    }
}
